#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    /**
     * @brief 两两交换链表中的节点
     * 第一个和第二个交换，第三个和第四个交换，etc...
     * 最后返回头节点
     */
    ListNode* swapPairs(ListNode* head) {
         if(head ==nullptr || head->next ==nullptr){
            return head;
        }
        ListNode* next = head->next;
        head->next = swapPairs(next->next);
        next->next = head;
        return next;
    }
};

int main()
{
    Solution solution;
    ListNode* f = new ListNode(1);
    ListNode* s = new ListNode(2);
    ListNode* t = new ListNode(3);
    ListNode* g = new ListNode(4);
    f->next = s;
    s->next = t;
    t->next = g;
    ListNode* n = solution.swapPairs(f);
    while(n!=nullptr){
        cout<<n->val<<' ';
        n = n->next;
    }
    cout<<endl;
    return 0;
}